5.2.1.2. En Küçük Eleman Bulma için T(n) Hesabı

Örnek: Aşağıda bir dizi içerisindeki en küçük elamanı bulan bulEnKucuk() adlı bir fonksiyonun kodu görülmektedir. Bu fonksiyonun yürütme zamanını gösteren T(n) bağıntısı ayrık C dili deyimlerine göre belirleyiniz.

float bulEnKucuk(float A[ ])   {      float enkucuk;      int k;        enkucuk=A[0];       /* ilk eleman en küçük varsayılıyor */    for(k=1; k<n; k++)          if(A[k]<enkucuk)                enkucuk=A[k];    return enkucuk;   }

Çözüm: Programdaki ayrık C dili deyimleri numaralandırılmış satırlardaki atama, karşılaştırma, aritmetik işlemler ve return ile sonuç gönderme işlemleridir. Buna göre, ve . satırlarda birer işlem yapılmaktadır. Dolayısıyla bu iki satırın etkisi sabit olarak 2'dir. . satırda ise bir for döngüsü vardır; döngü kapsamında yapılanlar hariç for deyimi içerisinde k=1; k<n, k++ gibi işlemler vardır. Bu işlemlerden ilki 1 kez, ikincisi (n) kez, üçüncüsü de (n-1) kez yapılır. Dolayısıyla, sadece for deyiminin yürütülmesi için 1+n+(n-1)=2n kez işlem yapılır. . satırda 1 tane karşılaştırma işlemi vardır ve bu işlem döngü çevrim sayısı kadar yürütülür; dolayısıyla işlem sayısı (n-1)'dir. . satırda ise bir atama işlemi vardır; bu işlem bir üstündeki karşılaştırma koşulu olumlu olduğu zaman yürütülür; olumsuz ise atlanır. Eğer dizinin ilk elemanı en küçük ise hiç yürütülmez. Dolayısıyla bu işlemin kaç kez yürütüleceği dizi elemanlarına bağlıdır. Ancak, en kötü durumda, her zaman koşulun olumlu olması durumun-da, döngü çevrim sayısı kadar gerçekleştirilir; burada işlem sayısının en kötü durumda (n-1) olduğu çıkarılır. Tüm bunlardan toplam işlem sayısını gösteren T(n), tüm satırlardaki işlem sayılarının toplamından bulunur.

. satırda 1 . satırda 2n . satırda n-1 . satırda n-1 . satırda 1     T(n) = 1+2n+(n-1)+(n-1)+1 = 3n+4

olarak bulunur.